package com.test.daily.leetcode.y2022.m07.day0701.v01;

/**
 * @author Tom on 2022/7/1
 */
public class Solution {
    public int maxCoin0(int[] arr) {
        int N = arr.length;
        int[] nums = new int[N + 2];
        for (int i = 0; i < N; i++) {
            nums[i + 1] = arr[i];
        }
        nums[0] = 1;
        nums[N + 1] = 1;
        return process0(nums, 1, N + 1);
    }

    public int process0(int[] arr, int L, int R) {
        if (L == R) {
            return arr[L - 1] * arr[L] * arr[R + 1];
        }
        int score = arr[L - 1] * arr[L] * arr[R + 1] + process0(arr, L + 1, R);
        score = Math.max(score, process0(arr, L, R - 1) + arr[L - 1] * arr[R] * arr[R + 1]);
        //中間的氣球爆掉
        for (int i = L + 1; i < R; i++) {
            score = Math.max(score, arr[L - 1] * arr[i] * arr[R + 1] + process0(arr, L, i - 1)
                    + process0(arr, i + 1, R));
        }
        return score;
    }

    public static int maxCoin1(int[] arr) {
        int N = arr.length;
        int[] help = new int[N + 2];
        for (int i = 0; i < N + 2; i++) {
            help[i + 1] = arr[i];
        }
        help[0] = 1;
        help[N + 1] = 1;
        int[][] dp = new int[N + 2][N + 2];
        for (int i = 0; i < N + 2; i++) {
            dp[i][i] = arr[i - 1] * arr[i] * arr[i + 1];
        }
        for (int L = N; L >= 1; L--) {
            for (int R = L+1; R <= N; R++) {
                int ans = arr[L - 1] * arr[L] * arr[R + 1] + dp[L + 1][R];
                ans = Math.max(ans, dp[L][R - 1] + arr[L - 1] * arr[R] * arr[R + 1]);
                for (int i = L + 1; i < R; i++) {
                    ans = Math.max(ans, dp[L][i - 1] + dp[i + 1][R]);
                }
                dp[L][R] = ans;
            }
        }
        return dp[1][N];
    }
}
